#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct Node
{
	long long l,r,val,sum,tag;
}edge[400005];
long long n,k,ans=0,a[100005],lst[100005],id[100005];
void build(long long u,long long l,long long r)
{
	edge[u].l=l,edge[u].r=r,edge[u].tag=0;
	if(l==r)
	{
		edge[u].val=0,edge[u].sum=1;
		return ;
	}
	long long mid=(edge[u].l+edge[u].r)>>1,ans=0,sum=0;
	build(u*2,l,mid),build(u*2+1,mid+1,r);
	ans=min(edge[u*2].val,edge[u*2+1].val);
	if(edge[u*2].val==ans)
	{
		sum+=edge[u*2].sum;
	}
	if(edge[u*2+1].val==ans)
	{
		sum+=edge[u*2+1].sum;
	}
	edge[u].val=ans,edge[u].sum=sum;
}
void change(long long u,long long l,long long r,long long v)
{
	if(l>r)
	{
		return ;
	}
	if(edge[u].l>=l&&edge[u].r<=r)
	{
		edge[u].val+=v,edge[u].tag+=v;
		return ;
	}
	if(edge[u].tag)
	{
		long long x=edge[u].tag;
		edge[u*2].val+=x,edge[u*2+1].val+=x;
		edge[u*2].tag+=x,edge[u*2+1].tag+=x;
		edge[u].tag=0;
	}
	long long mid=(edge[u].l+edge[u].r)>>1,ans=0,sum=0;
	if(l<=mid)
	{
		change(u*2,l,r,v);
	}
	if(mid<r)
	{
		change(u*2+1,l,r,v);
	}
	ans=min(edge[u*2].val,edge[u*2+1].val);
	if(edge[u*2].val==ans)
	{
		sum+=edge[u*2].sum;
	}
	if(edge[u*2+1].val==ans)
	{
		sum+=edge[u*2+1].sum;
	}
	edge[u].val=ans,edge[u].sum=sum;
}
int main()
{
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		lst[i]=id[a[i]];
		id[a[i]]=i;
	}
	for(long long x=1;x<=(1<<k)-1;x++)
	{
		long long cnt=0,sum=0;
		build(1,1,n);
		for(long long v=0;v<=k-1;v++)
		{
			if((x>>v)&1)
			{
				cnt++;
			}
		}
		for(long long i=1;i<=n;i++)
		{
			long long l=i;
			for(long long v=0;l&&v<=k-1;v++)
			{
				if((x>>v)&1)
				{
					change(1,lst[l]+1,l,1);
					change(1,lst[lst[l]]+1,lst[l],-1);
				}
				l=lst[l];
			}
			if(!edge[1].val)
			{
				sum+=n-edge[1].sum;
			}
			else
			{
				sum+=n;
			}
		}
		ans+=(cnt&1?1:-1)*sum;
	}
	cout<<ans<<endl;
	return 0;
}
